<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
        // 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
        /*
        实例：
        输入: nums = [-1,0,3,5,9,12], target = 9
        输出: 4
        解释: 9 出现在 nums 中并且下标为 4
        输入: nums = [-1,0,3,5,9,12], target = 2
        输出: -1
        解释: 2 不存在 nums 中因此返回 -1
        */

        //  将数组分为左右两个 边界  左 left 和 右 right 
        // 左闭右闭区间
        // 左边默认为0 右边为 arr.length-1
        /**那么他的中间值就是 左边的值 右边的值需要减去左边的值 
         mid=left+ Math.floor((right - left)/2)
        此中间值如果大于目标值  target在左边 right = mid - 1;
        此中间值如果小于目标值  target在右边 left = mid + 1;
        */


        function search(nums, target) {
            // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
            let left = 0, right = nums.length - 1;
            // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
            while (left <= right) {
                let mid = left + Math.floor((right - left) / 2);
                // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；如果右边界更新为mid，那中间数还在下次查找范围内
                if (nums[mid] > target) {
                    right = mid - 1;  // 去左面闭区间寻找
                } else if (nums[mid] < target) {
                    left = mid + 1;   // 去右面闭区间寻找
                } else {
                    return mid;
                }
            }
            return -1;
        };

        let nums = [-1, 0, 3, 5, 9, 12, 16]
        let target = 9
        console.log(search(nums, target));

        var sortedSquares = function (nums) {
            const n = nums.length;
            const ans = new Array(n).fill(0);

            let l = 0, r = n - 1;
            let i = n - 1;
            while (l <= r) {
                if (nums[l] * nums[l] > nums[r] * nums[r]) {
                    console.log(i,l,1);
                    ans[i--] = nums[l] * nums[l++];
                    console.log(i,l,2);
                } else {
                    ans[i--] = nums[r] * nums[r--];
                }
            }
            return ans;
        };


        console.log(sortedSquares([-4, -1, 0, 3, 10]), '123');
    </script>
</body>

</html>